原题地址：[x 的平方根](> https://leetcode-cn.com/problems/sqrtx/)
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入：8
输出：2
说明：8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
二分查找
题目要求返回的是整数，而且这个整数一定在$1$到$x$之间。所以我们可以利用查找算法找到这个数，它一定满足$n^2 \le x$且$(n+1)^2 > x$。由于查找范围有序，我们还可以利用二分查找来优化这一过程。
具体实现如下：
/**
* @param {number} x
* @return {number}
*/
const mySqrt1 = function(x) {
// 1的平方根为1
if (x === 1) {
return 1;
}
// 二分查找
let p = Math.floor(x/2);
let [left, right] = [1, x]; // 左右边界
while (true) {
if ( p * p === x) { // 找到了
return p;
} else if (p * p < x) {
if ((p + 1) * (p + 1) > x) {
// 当前数的平方小于x，而下一个数的平方又大于x，显然在两数中间
return p;
} else {
// 向右查找
left = p;
p = Math.floor((p + right) / 2)
}
} else {
// 向左查找
right = p;
p = Math.floor((p + left) / 2)
}
}
};
测试：
let start = new Date();
const test = mySqrt1;
console.log(test(8192)); // 90
console.log(test(8)); // 2
console.log(test(3)); // 1
console.log(test(1)); // 1
console.log(test(2)); // 1
console.log(new Date().getTime() - start.getTime()); // 8
时间复杂度： 二分查找，时间复杂度为$O(logN)$
空间复杂度： 常数级额外空间，空间复杂度为$O(1)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 20,2019